package DFSandBFS;
import java.util.*;
/**
 * 计算二维字符数组中岛屿的数量
 * 时间复杂度O(m*n)，空间复杂度O(m*n)，m和n为数组的行数和列数
 */
public class numIslands {
    /**
     * 计算二维字符数组中岛屿的数量
     * 
     * @param grid 二维字符数组，'1'表示陆地，'0'表示水域
     * @return 岛屿的数量
     */
    public static int numIslandsM(char[][] grid){
        int m = grid.length; // 获取数组的行数
        int n = grid[0].length; // 获取数组的列数
        int num = 0; // 初始化岛屿数量
        for(int i = 0; i < m; i++){ // 遍历数组的每一行
            for(int j = 0; j < n; j++){ // 遍历数组的每一列
                if(grid[i][j] == '1'){ // 如果当前字符为'1'，表示发现一个岛屿
                    dfs(grid, i, j); // 调用深度优先搜索方法标记该岛屿
                    num++; // 岛屿数量加1
                }
            }
        }
        return num; // 返回岛屿的数量
    }

    /**
     * 深度优先搜索方法，用于标记岛屿
     * 
     * @param grid 二维字符数组
     * @param i 当前行索引
     * @param j 当前列索引
     */
    public static void dfs(char[][] grid, int i, int j){
        if(i < 0 || i > grid.length - 1 || j < 0 || j > grid[0].length - 1) // 检查索引是否越界
            return; // 如果越界，返回
        if(grid[i][j] != '1') // 检查当前字符是否为'1'
            return; // 如果不是，返回
        grid[i][j] = '0'; // 标记当前字符为'0'，表示已访问
        dfs(grid, i - 1, j); // 递归检查上方
        dfs(grid, i + 1, j); // 递归检查下方
        dfs(grid, i, j - 1); // 递归检查左方
        dfs(grid, i, j + 1); // 递归检查右方
    }

    /**
     * 主函数：处理输入输出
     * 输入格式：第一行输入两个整数m和n，表示二维字符数组的行数和列数
     * 接下来m行，每行输入n个字符，表示二维字符数组
     * 输出格式：输出岛屿的数量
     */
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int m = sc.nextInt(); // 读取行数
        int n = sc.nextInt(); // 读取列数
        sc.nextLine(); // 读取换行符
        char[][] grid = new char[m][n]; // 创建二维字符数组
        for(int i = 0; i < m; i++){ // 读取每一行的字符
            String[] line = sc.nextLine().split(" "); // 分割输入的字符
            for(int j = 0; j < n; j++){ // 将字符存入数组
                grid[i][j] = line[j].charAt(0); // 将字符串转换为字符
            }
        }
        System.out.println(numIslandsM(grid)); // 输出岛屿的数量
        sc.close(); // 关闭输入流
    }
}
